{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize the Maximum of Two Arrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeSet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小化两个数组中的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个数组&nbsp;<code>arr1</code> 和&nbsp;<code>arr2</code>&nbsp;，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr1</code>&nbsp;包含&nbsp;<code>uniqueCnt1</code>&nbsp;个<strong>&nbsp;互不相同</strong>&nbsp;的正整数，每个整数都&nbsp;<strong>不能 </strong>被&nbsp;<code>divisor1</code>&nbsp;<strong>整除</strong>&nbsp;。</li>\n",
    "\t<li><code>arr2</code>&nbsp;包含&nbsp;<code>uniqueCnt2</code>&nbsp;个<strong>&nbsp;互不相同</strong>&nbsp;的正整数，每个整数都&nbsp;<strong>不能</strong>&nbsp;被&nbsp;<code>divisor2</code>&nbsp;<strong>整除</strong>&nbsp;。</li>\n",
    "\t<li><code>arr1</code> 和&nbsp;<code>arr2</code>&nbsp;中的元素&nbsp;<strong>互不相同</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你&nbsp;<code>divisor1</code>&nbsp;，<code>divisor2</code>&nbsp;，<code>uniqueCnt1</code>&nbsp;和&nbsp;<code>uniqueCnt2</code>&nbsp;，请你返回两个数组中&nbsp;<strong>最大元素</strong>&nbsp;的&nbsp;<strong>最小值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>\n",
    "我们可以把前 4 个自然数划分到 arr1 和 arr2 中。\n",
    "arr1 = [1] 和 arr2 = [2,3,4] 。\n",
    "可以看出两个数组都满足条件。\n",
    "最大值是 4 ，所以返回 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>\n",
    "arr1 = [1,2] 和 arr2 = [3] 满足所有条件。\n",
    "最大值是 3 ，所以返回 3 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2\n",
    "<b>输出：</b>15\n",
    "<b>解释：</b>\n",
    "最终数组为 arr1 = [1,3,5,7,9,11,13,15] 和 arr2 = [2,6] 。\n",
    "上述方案是满足所有条件的最优解。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= divisor1, divisor2 &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= uniqueCnt1, uniqueCnt2 &lt; 10<sup>9</sup></code></li>\n",
    "\t<li><code>2 &lt;= uniqueCnt1 + uniqueCnt2 &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-the-maximum-of-two-arrays](https://leetcode.cn/problems/minimize-the-maximum-of-two-arrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-the-maximum-of-two-arrays](https://leetcode.cn/problems/minimize-the-maximum-of-two-arrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n7\\n1\\n3', '3\\n5\\n2\\n1', '2\\n4\\n8\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True,\\\n",
    "                           key=lambda v: (v - v // d1 >= uniqueCnt1) and\\\n",
    "                           (v - v // d2 >= uniqueCnt2) and\\\n",
    "                           (v - v // lcm >= uniqueCnt1 + uniqueCnt2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        # 手玩一下\n",
    "        # d1 = 4, d2 = 6\n",
    "        # arr1     1 2 3   5 6 7   9 10 11   13...\n",
    "        # arr2     1 2 3 4 5   7 8 9 10 11   13...\n",
    "        # arr1 独占：6 的倍数，又不是 4 的倍数（或者说不能是 12的倍数）\n",
    "        # arr2 独占：4 的倍数，又不是 6 的倍数（或者说不能是 12的倍数）\n",
    "        # arr1 2 共享：既不是 4 的倍数又不是 6 的倍数\n",
    "        #             = 所有数的个数 - （4 的倍数 +6 的倍数 - 12 的倍数）\n",
    "\n",
    "        # 最大元素的最小值\n",
    "        #  答案越大，能选的数就越多，就越能组成满足要求的 arr1和 arr2\n",
    "        #  答案越小，能选的数就越少，就越不能组成满足要求的 arr1和 arr2\n",
    "        #  => 单调性\n",
    "        #  => 二分答案\n",
    "\n",
    "        # 最坏情况下，divisor1 = divisor2 = 2\n",
    "        # 只能选奇数\n",
    "        # uniqueCnt1 + uniqueCnt2 => (uniqueCnt1 + uniqueCnt2)*2 -1\n",
    "        lcm = math.lcm(d1, d2)      # 计算d1和 d2的最小公倍数  d1 = 4、d2 = 6的话，lcm=12\n",
    "\n",
    "        left = 0\n",
    "        right = (uniqueCnt1 + uniqueCnt2) * 2       # 开区间（left, right）\n",
    "        def check(x:int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - (x // d2 - x // lcm), 0)\n",
    "            left2 = max(uniqueCnt2 - (x // d1 - x // lcm), 0)\n",
    "            common = x - (x // d1 + x // d2 -x // lcm)\n",
    "            return common >= left1 + left2\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2           # 中间值\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b == 0: return a\n",
    "            return gcd(b, a % b)\n",
    "\n",
    "        lcm = (divisor1 * divisor2) // gcd(divisor1, divisor2)\n",
    "        \n",
    "        def check(m: int) -> bool:\n",
    "            s = m // lcm\n",
    "            c1, c2 =  m // divisor2 , m // divisor1\n",
    "            s, c1, c2 = m - c1 - c2 + s, c1 - s, c2 - s\n",
    "            return max(0, uniqueCnt1 - c1) + max(0, uniqueCnt2 - c2) <= s\n",
    "\n",
    "        l, r = 1, divisor1 * uniqueCnt1 + divisor2 * uniqueCnt2\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(divisor1, divisor2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // divisor2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // divisor1 + x // lcm, 0)\n",
    "            common = x - x // divisor1 - x // divisor2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        # 手玩一下\n",
    "        # d1 = 4, d2 = 6\n",
    "        # arr1     1 2 3   5 6 7   9 10 11   13...\n",
    "        # arr2     1 2 3 4 5   7 8 9 10 11   13...\n",
    "        # arr1 独占：6 的倍数，又不是 4 的倍数（或者说不能是 12的倍数）\n",
    "        # arr2 独占：4 的倍数，又不是 6 的倍数（或者说不能是 12的倍数）\n",
    "        # arr1 2 共享：既不是 4 的倍数又不是 6 的倍数\n",
    "        #             = 所有数的个数 - （4 的倍数 +6 的倍数 - 12 的倍数）\n",
    "\n",
    "        # 最大元素的最小值\n",
    "        #  答案越大，能选的数就越多，就越能组成满足要求的 arr1和 arr2\n",
    "        #  答案越小，能选的数就越少，就越不能组成满足要求的 arr1和 arr2\n",
    "        #  => 单调性\n",
    "        #  => 二分答案\n",
    "\n",
    "        # 最坏情况下，divisor1 = divisor2 = 2\n",
    "        # 只能选奇数\n",
    "        # uniqueCnt1 + uniqueCnt2 => (uniqueCnt1 + uniqueCnt2)*2 -1\n",
    "        lcm = math.lcm(d1, d2)      # 计算d1和 d2的最小公倍数  d1 = 4、d2 = 6的话，lcm=12\n",
    "\n",
    "        left = 0\n",
    "        right = (uniqueCnt1 + uniqueCnt2) * 2       # 开区间（left, right）\n",
    "        def check(x:int) -> bool:                                   # x是否可以拿还是有剩余还是不够\n",
    "            left1 = max(uniqueCnt1 - (x // d2 - x // lcm), 0)       # arr1还需要left1个， 拿到了x2不要的但是x1能拿的 还需要left1个\n",
    "            left2 = max(uniqueCnt2 - (x // d1 - x // lcm), 0)       # arr2还需要left2个   拿到了x1不要的但是x2能拿的 还需要left2个\n",
    "            common = x - (x // d1 + x // d2 -x // lcm)              # 能选的个数\n",
    "            return common >= left1 + left2          # 能选的个数大于等于这两个数的剩余需要的个数之和 从1开始到x中间可以拿的是common个，需要l1+l2个\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2           # 中间值\n",
    "            if check(mid):              # 能选的大于需要 在left和mid范围\n",
    "                right = mid\n",
    "            else:                       # 能选的小于需要 在mid和right范围\n",
    "                left = mid\n",
    "        return right\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, cnt1: int, cnt2: int) -> int:\n",
    "        \"\"\"\n",
    "        :type divisor1: int\n",
    "        :type divisor2: int\n",
    "        :type uniqueCnt1: int\n",
    "        :type uniqueCnt2: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(n) -> bool:\n",
    "            # 在该函数内部只需要判断 1~n能不能挑出cnt1+cnt2个数放入两个集合 即可\n",
    "            only_put_1_num = int(n/d2) - int(n/lcm)\n",
    "            only_put_2_num = int(n/d1) - int(n/lcm)\n",
    "            share_num = n - int(n/d1) - int(n/d2) + int(n/lcm)\n",
    "            need_put_1_num = max(cnt1 - only_put_1_num, 0)\n",
    "            need_put_2_num = max(cnt2 - only_put_2_num, 0)\n",
    "            return share_num >= need_put_1_num + need_put_2_num\n",
    "            \n",
    "        # 找从左往右起第一个True即可\n",
    "        return bisect_left(range((cnt1+cnt2)*2), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x):\n",
    "            r1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            r2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common  >= r1 + r2\n",
    "        return bisect_left(range(2 * (uniqueCnt1 + uniqueCnt2) - 1), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            while b != 0:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        divisor3 = divisor1 * divisor2 // gcd(divisor1, divisor2)\n",
    "        uniqueCnt3 = uniqueCnt1 + uniqueCnt2\n",
    "        left = uniqueCnt1 + uniqueCnt2\n",
    "        right = left * 2\n",
    "        while left < right:\n",
    "            m = (left + right) // 2\n",
    "            if m - m // divisor1 >= uniqueCnt1 and m - m // divisor2 >= uniqueCnt2 and m - m // divisor3 >= uniqueCnt3:\n",
    "                right = m\n",
    "            else:\n",
    "                left = m + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b == 0: return a\n",
    "            return gcd(b, a % b)\n",
    "\n",
    "        lcm = (divisor1 * divisor2) // gcd(divisor1, divisor2)\n",
    "        \n",
    "        def check(m: int) -> bool:\n",
    "            s = m // lcm\n",
    "            c1, c2 =  m // divisor2 , m // divisor1\n",
    "            s, c1, c2 = m - c1 - c2 + s, c1 - s, c2 - s\n",
    "            return max(0, uniqueCnt1 - c1) + max(0, uniqueCnt2 - c2) <= s\n",
    "\n",
    "        l, r = 1, 2000_000_000\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def f(x):\n",
    "            cnt1 = x // divisor1 * (divisor1 - 1) + x % divisor1\n",
    "            cnt2 = x // divisor2 * (divisor2 - 1) + x % divisor2\n",
    "            cnt = x // divisor * (divisor - 1) + x % divisor\n",
    "            return (\n",
    "                cnt1 >= uniqueCnt1\n",
    "                and cnt2 >= uniqueCnt2\n",
    "                and cnt >= uniqueCnt1 + uniqueCnt2\n",
    "            )\n",
    "\n",
    "        divisor = lcm(divisor1, divisor2)\n",
    "        return bisect_left(range(10**10), True, key=f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        # 正好交叉替换，A组不要的给B，B不要的而给A，最小公倍数不能要\n",
    "        part = uniqueCnt1+uniqueCnt2\n",
    "        lcm = divisor1*divisor2//math.gcd(divisor1, divisor2)\n",
    "        res1 = (lcm * part-1)//(lcm-1)\n",
    "        # A组很长，过程中不要的已经可以填满B了，因此只要考虑A就可以了\n",
    "        res2 = (divisor1 * uniqueCnt1 -1)//(divisor1-1)\n",
    "        # B组很长，过程中不要的已经可以填满A了，因此只要考虑B就可以了\n",
    "        res3 = (divisor2 * uniqueCnt2 -1)//(divisor2-1)\n",
    "        return max(res1,res2, res3)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def cal(val, d):\n",
    "            return val - val // d\n",
    "\n",
    "        l, r = 1, 10** 15\n",
    "\n",
    "        d1 = divisor1\n",
    "        d2 = divisor2\n",
    "        dlcm = lcm(d1, d2)\n",
    "\n",
    "        ans = None\n",
    "        while l <= r:\n",
    "            m = (l + r) >> 1\n",
    "\n",
    "            va = cal(m, d1)      # 不能被d1整除的\n",
    "            vb = cal(m, d2)      # 不能被d2整除的\n",
    "            v = m - m//d1 - m//d2 + m//dlcm       # 不能被d1整除也不能被d2整除的\n",
    "            if max(uniqueCnt1-(va-v), 0) + max(uniqueCnt2-(vb-v), 0) <= v:\n",
    "                ans = m\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(divisor1, divisor2)\n",
    "        def check(target):\n",
    "            cnt_both = target // lcm\n",
    "            cnt_div1 = target // divisor1 - cnt_both\n",
    "            cnt_div2 = target // divisor2 - cnt_both\n",
    "\n",
    "            tmp_cnt1 = max(0, uniqueCnt1 - cnt_div2)\n",
    "            tmp_cnt2 = max(0, uniqueCnt2 - cnt_div1)\n",
    "\n",
    "            return target - target//divisor1 - target // divisor2 + cnt_both >= tmp_cnt1 + tmp_cnt2\n",
    "\n",
    "        \n",
    "        check(15)\n",
    "        i = 0\n",
    "        j = int(2e9)\n",
    "\n",
    "        while i < j-1:\n",
    "            mid = (i + j) // 2\n",
    "            if check(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid + 1\n",
    "        if check(i):\n",
    "            return i\n",
    "        return j\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(\n",
    "        self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int\n",
    "    ) -> int:\n",
    "        if divisor1 > divisor2:\n",
    "            divisor1, divisor2 = divisor2, divisor1\n",
    "            uniqueCnt1, uniqueCnt2 = uniqueCnt2, uniqueCnt1\n",
    "        l = 0\n",
    "        # r = 2 * 10**9\n",
    "        r = (uniqueCnt1 + uniqueCnt2) * 2  # Wrong case: d1 = d2 = 2\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            a = mid // divisor1\n",
    "            b = mid // divisor2\n",
    "            c = mid // (lcm(divisor1, divisor2))\n",
    "            # print(mid, a, b, c)\n",
    "            if (\n",
    "                mid - a >= uniqueCnt1\n",
    "                and mid - b >= uniqueCnt2\n",
    "                and mid - c >= uniqueCnt1 + uniqueCnt2\n",
    "            ):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        # 得到最小公倍数\n",
    "        lcm = math.lcm(divisor1, divisor2)\n",
    "        # 辅助函数 如果每个数组数量够就返回True\n",
    "        def check(x):\n",
    "            # 能在l1但不能在l2中的数量 不能被d1整除但能被d2整除\n",
    "            l1 = max(0, uniqueCnt1 - x // divisor2 + x // lcm)\n",
    "            l2 = max(0, uniqueCnt2 - x // divisor1 + x // lcm)\n",
    "            common = x - x // divisor1 - x // divisor2 + x // lcm\n",
    "            return common >= l1 + l2\n",
    "        l, r = 1, 2 * int(1e9)\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, u1: int, u2: int) -> int:\n",
    "        def check(self, d1: int, d2: int, u1: int, u2: int, x: int):\n",
    "            c = x // lcm(d1, d2)\n",
    "            r1 = x // d1 - c\n",
    "            r2 = x // d2 - c\n",
    "            print(f\"x:{x} r1:{r1} r2:{r2}\")\n",
    "            return x - r1 - r2 - c >= max(u1 - r2, 0) + max(u2 - r1, 0)\n",
    "        \n",
    "        l, r = 0, (u1 + u2) * 2 + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, d1, d2, u1, u2, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(divisor1, divisor2)\n",
    "        def check(x):\n",
    "            left1 = max(uniqueCnt1 - x //divisor2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // divisor1 + x // lcm, 0)\n",
    "            common = x - x // divisor1 - x // divisor2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        \n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 -1), True, key=check)\n",
    "\n",
    "        # l, r = 0, int(1e9) + 1\n",
    "        # while l + 1 < r:\n",
    "        #     mid = (r+l) // 2\n",
    "        #     arr1 = []\n",
    "        #     arr2 = []\n",
    "        #     if check(mid):\n",
    "        #         r = mid\n",
    "        #     else:\n",
    "        #         l = mid\n",
    "        # return r\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        d = math.lcm(divisor1, divisor2)\n",
    "        def check(mid):\n",
    "            x = mid // divisor2\n",
    "            y = mid // divisor1\n",
    "            k = mid // d\n",
    "            s = mid - x - y + k\n",
    "            return s >= max(uniqueCnt1 - x + k, 0) + max(uniqueCnt2 - y + k, 0)\n",
    "\n",
    "        l, r = 2, 10 ** 10 + 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        left=1\n",
    "        right=(uniqueCnt1+uniqueCnt2)*2\n",
    "        lcm=math.lcm(d1,d2)\n",
    "        def check(x:int) -> bool:\n",
    "            left1=max(uniqueCnt1-x//d2+x//lcm,0)\n",
    "            left2=max(uniqueCnt2-x//d1+x//lcm,0)\n",
    "            common=x-x//d1-x//d2+x//lcm\n",
    "            return common>=left1+left2\n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def check(x):\n",
    "            cnt1 = x - x // divisor1\n",
    "            cnt2 = x - x // divisor2\n",
    "            common = x - x // lcm\n",
    "            return cnt1 >= uniqueCnt1 and cnt2 >= uniqueCnt2 and common >= uniqueCnt1 + uniqueCnt2 \n",
    "        \n",
    "        lcm = math.lcm(divisor1, divisor2)\n",
    "        l, r = 0, 0x3f3f3f3f * 2\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if not check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        left = uniqueCnt1 + uniqueCnt2\n",
    "        right = int(1e14)\n",
    "\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        def check(tar):\n",
    "            cnt1 = tar // divisor1\n",
    "            cnt2 = tar // divisor2\n",
    "\n",
    "            lcm = divisor1 * divisor2 // gcd(divisor1, divisor2)\n",
    "\n",
    "            cnt3 = tar // lcm\n",
    "\n",
    "            total = tar\n",
    "\n",
    "            p1 = total - cnt1\n",
    "            p2 = total - cnt2\n",
    "            overlap = total - (cnt1 + cnt2 - cnt3)\n",
    "\n",
    "            # x1 = p1\n",
    "            # x2 = p2 - overlap\n",
    "\n",
    "            # y1 = p1 - overlap\n",
    "            # y2 = p2\n",
    "\n",
    "            # return y1 <= uniqueCnt1 <= x1 and x2 <= uniqueCnt2 <= y2\n",
    "\n",
    "            p1 -= overlap\n",
    "            p2 -= overlap\n",
    "\n",
    "            if p1 >= uniqueCnt1 and p2 >= uniqueCnt2:\n",
    "                return True\n",
    "            \n",
    "            if p1 < uniqueCnt1 and p2 < uniqueCnt2:\n",
    "                return overlap >= (uniqueCnt1 - p1 + uniqueCnt2 - p2)\n",
    "\n",
    "            if p1 >= uniqueCnt1 and p2 < uniqueCnt2:\n",
    "                return overlap >= (uniqueCnt2 - p2)\n",
    "\n",
    "            if p2 >= uniqueCnt2 and p1 < uniqueCnt1:\n",
    "                return overlap >= (uniqueCnt1 - p1)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(\n",
    "        self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int\n",
    "    ) -> int:\n",
    "        if divisor1 > divisor2:\n",
    "            divisor1, divisor2 = divisor2, divisor1\n",
    "            uniqueCnt1, uniqueCnt2 = uniqueCnt2, uniqueCnt1\n",
    "        l = 0\n",
    "        r = 2 * 10**9\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            a = mid // divisor1\n",
    "            b = mid // divisor2\n",
    "            c = mid // (lcm(divisor1, divisor2))\n",
    "            # print(mid, a, b, c)\n",
    "            if (\n",
    "                mid - a >= uniqueCnt1\n",
    "                and mid - b >= uniqueCnt2\n",
    "                and mid - c >= uniqueCnt1 + uniqueCnt2\n",
    "            ):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if a < b:\n",
    "                a, b = b, a\n",
    "            if a%b==0:\n",
    "                return b\n",
    "            else:\n",
    "                return gcd(b, a%b)\n",
    "        def check(n, lcm):\n",
    "            positionFor1 = n-n//divisor1\n",
    "            positionFor2 = n-n//divisor2\n",
    "            commonPosition = positionFor1 + positionFor2 - (n-n//lcm)\n",
    "            onlyFor1 = positionFor1 - commonPosition\n",
    "            onlyFor2 = positionFor2 - commonPosition\n",
    "            if uniqueCnt1 < onlyFor1:\n",
    "                return uniqueCnt2 <= positionFor2\n",
    "            elif uniqueCnt2 < onlyFor2:\n",
    "                return uniqueCnt1 <= positionFor1\n",
    "            else:\n",
    "                return uniqueCnt1 + uniqueCnt2 - onlyFor1 - onlyFor2 <= commonPosition\n",
    "        max1 = uniqueCnt1 // (divisor1 - 1) * divisor1 + uniqueCnt1 % divisor1\n",
    "        max2 = uniqueCnt2 // (divisor2 - 1) * divisor2 + uniqueCnt2 % divisor2\n",
    "        low = 1\n",
    "        high = 2*(max1 + max2 + 2)\n",
    "        lcm = divisor1*divisor2//gcd(divisor1,divisor2)\n",
    "        while high - low > 1:\n",
    "            mid = (high + low)//2\n",
    "            if check(mid, lcm):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        if check(low, lcm):\n",
    "            return low\n",
    "        else:\n",
    "            return high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        # 最大元素的最小值，二分法\n",
    "        # 上界怎么求： divisor1=divisor2=2 的时候最极端，right = (uniqueCnt1+uniqueCnt2)//2\n",
    "        # 找到 [0, mid] 中分别能被divisor1,divisor2整除，以及共同整除的数 \n",
    "        left, right = (uniqueCnt1+uniqueCnt2), (uniqueCnt1+uniqueCnt2)*2\n",
    "        lcm = math.lcm(divisor1, divisor2) # 最小公倍数\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            cnt1 = mid//divisor2 - mid//lcm   # 1号中独有的数\n",
    "            cnt2 = mid//divisor1 - mid//lcm   # 2号中独有的数\n",
    "            cnt3 = mid-mid//divisor1-mid//divisor2+mid//lcm    # 既可以在1号也可以在2号\n",
    "            if cnt3>=max(uniqueCnt1-cnt1, 0)+max(uniqueCnt2-cnt2,0):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, u1: int, u2: int) -> int:\n",
    "        def check(self, d1: int, d2: int, u1: int, u2: int, x: int):\n",
    "            c = x // lcm(d1, d2)\n",
    "            r1 = x // d1 - c\n",
    "            r2 = x // d2 - c\n",
    "            return x - r1 - r2 - c >= max(u1 - r2, 0) + max(u2 - r1, 0)\n",
    "        \n",
    "        l, r = 0, (u1 + u2) * 2 + 1\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(self, d1, d2, u1, u2, m):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        l, r = 0, (uniqueCnt1+uniqueCnt2)*2-1\n",
    "        lcm = math.lcm(divisor1, divisor2) # 最小公倍数\n",
    "\n",
    "        def check(m):\n",
    "            t1 = m//divisor1 #整除d1的个数\n",
    "            t2 = m//divisor2\n",
    "            tlcm = m//lcm\n",
    "            res1 = max(uniqueCnt1-(t2-tlcm), 0)\n",
    "            res2 = max(uniqueCnt2-(t1-tlcm), 0)\n",
    "            common = m - t1 - t2 +tlcm\n",
    "            return common >= res1+res2\n",
    "           \n",
    "\n",
    "        while l <= r:\n",
    "            m = (l + r)//2\n",
    "            if check(m):\n",
    "                r = m-1\n",
    "            else:\n",
    "                l = m+1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def gcd(a, b):\n",
    "            if b == 0: return a\n",
    "            return gcd(b, a % b)\n",
    "\n",
    "        lcm = (divisor1 * divisor2) // gcd(divisor1, divisor2)\n",
    "        \n",
    "        def check(m: int) -> bool:\n",
    "            s = m // lcm\n",
    "            c1, c2 =  m // divisor2 , m // divisor1\n",
    "            s, c1, c2 = m - c1 - c2 + s, c1 - s, c2 - s\n",
    "            return max(0, uniqueCnt1 - c1) + max(0, uniqueCnt2 - c2) > s\n",
    "\n",
    "        l, r = 1, 2000_000_000\n",
    "        while l < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, cnt1: int, cnt2: int) -> int:\n",
    "\n",
    "        def check(m):\n",
    "            not_1_or_2    = m // math.lcm(d1,d2) # 最小公倍数math.lcm(a,b)\n",
    "            only_put_in_1 = m // d2 - not_1_or_2\n",
    "            only_put_in_2 = m // d1 - not_1_or_2\n",
    "            share         = m - (only_put_in_1 + only_put_in_2 + not_1_or_2)\n",
    "            if only_put_in_1 >= cnt1 and only_put_in_2 >= cnt2:\n",
    "                return True\n",
    "            elif only_put_in_1 >= cnt1 and only_put_in_2 < cnt2:\n",
    "                return share >= cnt2 - only_put_in_2\n",
    "            elif only_put_in_2 >= cnt2 and only_put_in_1 < cnt1:\n",
    "                return share >= cnt1 - only_put_in_1\n",
    "            else:\n",
    "                return share >= cnt1 - only_put_in_1 + \\\n",
    "                                cnt2 - only_put_in_2\n",
    "                \n",
    "        return bisect_left(range((cnt1+cnt2)*2), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        l, r = 1, (uniqueCnt1 + uniqueCnt2) * divisor1 * divisor2\n",
    "        dlcm = math.lcm(divisor1, divisor2)\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            d1 = m - m // divisor1\n",
    "            d2 = m - m // divisor2\n",
    "            x = m - m // divisor1 - m // divisor2 + m // dlcm\n",
    "            if x >= max(uniqueCnt1 - (d1 - x), 0) + max(uniqueCnt2 - (d2 - x), 0):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, a: int, b: int, n: int, m: int) -> int:\n",
    "        lcm = math.lcm(a, b)\n",
    "        def valid(x):\n",
    "            i = x // a\n",
    "            j = x // b\n",
    "            k = x // lcm\n",
    "            return x - i - j + k >= max(n - j + k, 0) + max(m - i + k, 0)\n",
    "        low, high = 2, int((m + n) / (1 - (1 / a)  - (1 / b) + (1 / lcm)))\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            if valid(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid + 1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def check(max_ele):\n",
    "            num_div1 = max_ele // divisor1\n",
    "            num_div2 = max_ele // divisor2\n",
    "            num_both = max_ele // (divisor1 * divisor2 // gcd(divisor1, divisor2))\n",
    "            num_both_not = max_ele - num_div1 - num_div2 + num_both\n",
    "            num_div1_not_only = max_ele - num_div1 - num_both_not\n",
    "            num_div2_not_only = max_ele - num_div2 - num_both_not\n",
    "            # print(max_ele, num_both, num_both_not, num_div1_not_only, num_div2_not_only)\n",
    "            gap1 = max(uniqueCnt1 - num_div1_not_only, 0)\n",
    "            gap2 = max(uniqueCnt2 - num_div2_not_only, 0)\n",
    "            return gap1 + gap2 <= num_both_not\n",
    "        \n",
    "        left, right = 0, (uniqueCnt1 + uniqueCnt2) * 5\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            valid = check(mid)\n",
    "            if not valid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, cnt1: int, cnt2: int) -> int:\n",
    "        # 这是一种if语句的写法 更容易让自己理解\n",
    "        def check(m):\n",
    "            not_1_or_2    = m // math.lcm(d1,d2) # 最小公倍数math.lcm(a,b)\n",
    "            only_put_in_1 = m // d2 - not_1_or_2\n",
    "            only_put_in_2 = m // d1 - not_1_or_2\n",
    "            share         = m - (only_put_in_1 + only_put_in_2 + not_1_or_2)\n",
    "            if only_put_in_1 >= cnt1 and only_put_in_2 >= cnt2:\n",
    "                return True\n",
    "            elif only_put_in_1 >= cnt1 and only_put_in_2 < cnt2:\n",
    "                return share >= cnt2 - only_put_in_2\n",
    "            elif only_put_in_2 >= cnt2 and only_put_in_1 < cnt1:\n",
    "                return share >= cnt1 - only_put_in_1\n",
    "            else:\n",
    "                return share >= cnt1 - only_put_in_1 + \\\n",
    "                                cnt2 - only_put_in_2\n",
    "                \n",
    "        return bisect_left(range((cnt1+cnt2)*2), True, key=check)\n",
    "        # 答案最大值是(cnt1+cnt2)*2 这是重要的\n",
    "        # d1、d2的值越小，不能用的值越多，答案minmax值越大，越不利\n",
    "        # 最不利情况下因为最坏情况下 d1=d2=2,只有奇数能放入 \n",
    "        # cnt1+cnt2个奇数将使得答案达到(cnt1+cnt2)*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, u1: int, u2: int) -> int:\n",
    "        def check(x):\n",
    "            lcm = (d1 * d2)//math.gcd(d1,d2) \n",
    "            return (x - x//d1 - x//d2 + x//lcm)>= max(u1 - x//d2 + x//lcm, 0) + max(u2 - x//d1 + x//lcm, 0) \n",
    "        l, r = u1 + u2, int(4e9)\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lcm(self, a: int, b: int) -> int:\n",
    "        orig_a = a\n",
    "        orig_b = b\n",
    "        if a < b:\n",
    "            a, b = b, a\n",
    "        while b != 0:\n",
    "            a, b = b, a % b\n",
    "        return orig_a * orig_b // a\n",
    "\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        l = self.lcm(divisor1, divisor2)\n",
    "        def legal(upper: int) -> bool:\n",
    "            lcm_cnt = upper // l\n",
    "            a1_only = upper // divisor2 - lcm_cnt\n",
    "            a2_only = upper // divisor1 - lcm_cnt\n",
    "            return upper - a1_only - a2_only - lcm_cnt >= max(uniqueCnt1 - a1_only, 0) + max(uniqueCnt2 - a2_only, 0)\n",
    "\n",
    "        lo = -1\n",
    "        hi = (uniqueCnt1 + uniqueCnt2) * 2\n",
    "        while lo + 1 != hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if legal(mid):\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid\n",
    "        return hi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        l, r = uniqueCnt1+uniqueCnt2, (uniqueCnt1 + uniqueCnt2) * 2\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if not check(m):\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return l\n",
    "        # return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        mul = divisor1 * divisor2 // gcd(divisor1, divisor2)\n",
    "        min1, min2 = mul // divisor2 - 1, mul // divisor1 - 1\n",
    "        # n * mul + r\n",
    "        # n * min1, (n+1)*max1< u1\n",
    "        # print(mul, min1, min2)\n",
    "        # n <= u1 // min1\n",
    "        l = uniqueCnt1 + uniqueCnt2 - 1\n",
    "        r = 10**10\n",
    "        while r - l > 1:\n",
    "            m = (l + r)>>1\n",
    "            excluded = m // mul\n",
    "            d2, d1 = m // divisor1 - excluded, m // divisor2 - excluded\n",
    "            other = m - d1 - d2 - excluded\n",
    "            # print(l, r, m, d1, d2, other, excluded)\n",
    "            if other >= max(uniqueCnt1-d1, 0) + max(uniqueCnt2 - d2, 0):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm=math.lcm(divisor1,divisor2)\n",
    "        left=0\n",
    "        right=(uniqueCnt1+uniqueCnt2)*2\n",
    "        def check(x:int)->bool:\n",
    "            left1=max(uniqueCnt1-x//divisor2+x//lcm,0)\n",
    "            left2=max(uniqueCnt2-x//divisor1+x//lcm,0)\n",
    "            common=x-x//divisor1-x//divisor2+x//lcm\n",
    "            return common>=left1+left2\n",
    "        while left+1<right:\n",
    "            mid=(left+right)>>1\n",
    "            if check(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "\n",
    "\n",
    "        d3=divisor1*divisor2//(math.gcd(divisor1,divisor2))\n",
    "\n",
    "        def  check(t):\n",
    "            x1=t//divisor2-t//d3 \n",
    "            x2=t//divisor1-t//d3 \n",
    "            good1=max(0,uniqueCnt1-x1)\n",
    "            good2=max(0,uniqueCnt2-x2)\n",
    "            good3=t - t//divisor1 -t//divisor2+t//d3\n",
    "            if good3>=good1+good2:\n",
    "                return True\n",
    "        r=5*10**9\n",
    "        l=0\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid \n",
    "        if check(l):\n",
    "            return l\n",
    "        return r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(self, a: int, b: int) -> int:\n",
    "        while b != 0:\n",
    "            tmp = a % b\n",
    "            a = b\n",
    "            b = tmp\n",
    "        return a\n",
    "\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            x1 = mid // divisor2 - mid // lcm\n",
    "            x2 = mid // divisor1 - mid // lcm\n",
    "            need1 = max(0, uniqueCnt1 - x1)\n",
    "            need2 = max(0, uniqueCnt2 - x2)\n",
    "            x12 = mid - mid // divisor1 - mid // divisor2 + mid // lcm\n",
    "            return x12 >= need1 + need2\n",
    "        \n",
    "        lcm = divisor1 * divisor2 // self.gcd(divisor1, divisor2)\n",
    "\n",
    "        l = 1\n",
    "        r = 10 ** 9 * 2\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(self, a: int, b: int) -> int:\n",
    "        while b != 0:\n",
    "            tmp = a % b\n",
    "            a = b\n",
    "            b = tmp\n",
    "        return a\n",
    "\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            x1 = mid // divisor2 - mid // lcm\n",
    "            x2 = mid // divisor1 - mid // lcm\n",
    "            need1 = max(0, uniqueCnt1 - x1)\n",
    "            need2 = max(0, uniqueCnt2 - x2)\n",
    "            x12 = mid - mid // divisor1 - mid // divisor2 + mid // lcm\n",
    "            return x12 >= need1 + need2\n",
    "        \n",
    "        lcm = divisor1 * divisor2 // self.gcd(divisor1, divisor2)\n",
    "\n",
    "        l = 1\n",
    "        r = divisor1 * divisor2 * lcm *(uniqueCnt1 + uniqueCnt2) //(divisor1*divisor2*lcm - divisor1*lcm - divisor2*lcm + divisor1 * divisor2)\n",
    "        r = r + 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid) == True:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(self,a,b):\n",
    "        if a<b:\n",
    "            a,b=b,a\n",
    "        \n",
    "        while a%b!=0:\n",
    "            a,b=b,a%b\n",
    "        return b\n",
    "\n",
    "\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "\n",
    "        #这里存在多个变化量，可以考虑能不能其中一部分，只探讨个别几个变量\n",
    "        #假设d1,d2,u2固定，那此时最大元素的最小值显然随着u1的增大而增大\n",
    "        #反过来，随着最大元素的增大，u1也会不断增大，这样第一个满足u1要求的的最大元素即使最小值\n",
    "\n",
    "        #现在就是如何在给定最大元素，d1,d2,u2的情况下，找到最多的u1\n",
    "        #这里也可以采用贪心策略，首先找到target范围能被d1整除的数，然后将这数中不能被d2整除的数归到u2中去\n",
    "        # u1=target-(target中能够被d1整除的数的数量)-(u2-target中能够被d1整除的数中不能被d2整除的数的数量)\n",
    "\n",
    "        def check(target):\n",
    "            num1=int(target/divisor1)\n",
    "            num3=int(target/divisor2)\n",
    "\n",
    "            #判断是否有公因子\n",
    "            g=self.gcd(divisor1,divisor2)\n",
    "            num2=int(num1/(divisor2/g))\n",
    "\n",
    "            # if target-num1-(num3-num2)-(uniqueCnt2-num1+num2)<0:\n",
    "            #     return 0\n",
    "            # else:\n",
    "            return target-num1-max((uniqueCnt2-num1+num2),0)\n",
    "            \n",
    "        if uniqueCnt2%(divisor2-1)==0:\n",
    "            min_=int(uniqueCnt2/(divisor2-1))*divisor2-1\n",
    "        else:\n",
    "            min_=int(uniqueCnt2/(divisor2-1))*divisor2+uniqueCnt2%(divisor2-1)\n",
    "\n",
    "        \n",
    "        return bisect_left(range(min_,min(divisor1,divisor2)*(uniqueCnt1+uniqueCnt2)+1),uniqueCnt1,key=check)+min_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        m = divisor1 * divisor2 // gcd(divisor1,divisor2)\n",
    "        p = uniqueCnt1 + uniqueCnt2\n",
    "        def check(x):\n",
    "            res = x\n",
    "            ans = x\n",
    "            res -= x // divisor1\n",
    "            ans -= x // divisor2\n",
    "            t = x - x // m\n",
    "            if t >= p and res >= uniqueCnt1 and ans >= uniqueCnt2:\n",
    "                return True\n",
    "            return False\n",
    "        l,r = 0,int(1e15)\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l              \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        d12 = divisor1 * divisor2 // (math.gcd(divisor1, divisor2))\n",
    "        def cnt(n):\n",
    "            n12 = n // d12\n",
    "            n1 = n // divisor1 - n12\n",
    "            n2 = n // divisor2 - n12\n",
    "            n0 = n - n12 - n1 - n2\n",
    "            return n0 + n2 >= uniqueCnt1 and n0 + n1 >= uniqueCnt2 and n - n12 >= uniqueCnt1 + uniqueCnt2\n",
    "\n",
    "        left, right = uniqueCnt1 + uniqueCnt2 - 1, 3 * (uniqueCnt1 + uniqueCnt2)\n",
    "        while left < right - 1:\n",
    "            mid = (left + right) // 2\n",
    "            if cnt(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\r\n",
    "        # least common multiple\r\n",
    "        lcm = math.lcm(divisor1, divisor2)\r\n",
    "        \r\n",
    "        def check(x:int) -> bool:\r\n",
    "            # 找到最小的x，使其满足\r\n",
    "            left1 = max(0, uniqueCnt1 - x//divisor2 + x//lcm)\r\n",
    "            left2 = max(0, uniqueCnt2 - x//divisor1 + x//lcm)\r\n",
    "            common = x - x//divisor1 - x//divisor2 + x//lcm\r\n",
    "            return common >= left1 + left2\r\n",
    "        \r\n",
    "        return bisect_left(range(2*(uniqueCnt1+uniqueCnt2)-1), True, key=check)\r\n",
    "\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def gcd(self, a: int, b: int) -> int:\n",
    "        while b != 0:\n",
    "            tmp = a % b\n",
    "            a = b\n",
    "            b = tmp\n",
    "        return a\n",
    "\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            x1 = mid // divisor2 - mid // lcm\n",
    "            x2 = mid // divisor1 - mid // lcm\n",
    "            need1 = max(0, uniqueCnt1 - x1)\n",
    "            need2 = max(0, uniqueCnt2 - x2)\n",
    "            x12 = mid - mid // divisor1 - mid // divisor2 + mid // lcm\n",
    "            return x12 >= need1 + need2\n",
    "        \n",
    "        lcm = divisor1 * divisor2 // self.gcd(divisor1, divisor2)\n",
    "\n",
    "        l = 1\n",
    "        r = divisor1 * divisor2 * lcm *(uniqueCnt1 + uniqueCnt2) //(divisor1*divisor2*lcm - divisor1*lcm - divisor2*lcm + divisor1 * divisor2)\n",
    "        r = r + 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        left, right = 1, (uniqueCnt1 + uniqueCnt2) * 2 - 1\n",
    "        lc = lcm(divisor1, divisor2)\n",
    "        def check(mid):\n",
    "            need1 = max(uniqueCnt1 - mid // divisor2 + mid // lc, 0)\n",
    "            need2 = max(uniqueCnt2 - mid // divisor1 + mid // lc, 0)\n",
    "            cnt = mid -  mid // divisor1 - mid // divisor2 + mid // lc\n",
    "            return cnt >= need1 + need2\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            if check(mid): right = mid\n",
    "            else: left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, u1: int, u2: int) -> int:\n",
    "        def gcd(x, y):\n",
    "            if x == 0:\n",
    "                return y\n",
    "            else:\n",
    "                return gcd(y % x, x)\n",
    "        def check(num):\n",
    "            n1 = num // d1\n",
    "            n2 = num // d2\n",
    "            n_t = num // ((d1 * d2) // gcd(d1, d2))\n",
    "            # print(n1, n2, n_t, num)\n",
    "            if num - n1 < u1 or num - n2 < u2:\n",
    "                return False\n",
    "            if num - n_t < u1 + u2:\n",
    "                return False\n",
    "            \n",
    "            return True\n",
    "            \n",
    "            \n",
    "        l = 0\n",
    "        r = 2 * 10 ** 9\n",
    "        while l < r:\n",
    "            mid = (l + r) >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(divisor1, divisor2)\n",
    "\n",
    "        def check(x):\n",
    "            l1 = max(uniqueCnt1 - x // divisor2 + x // lcm, 0)\n",
    "            l2 = max(uniqueCnt2 - x // divisor1 + x // lcm, 0)\n",
    "            common = x - x // divisor1 - x // divisor2 + x // lcm\n",
    "            return common >= l1 + l2\n",
    "        \n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 + 1), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, d1: int, d2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        lcm = math.lcm(d1, d2)\n",
    "        def check(x: int) -> bool:\n",
    "            left1 = max(uniqueCnt1 - x // d2 + x // lcm, 0)\n",
    "            left2 = max(uniqueCnt2 - x // d1 + x // lcm, 0)\n",
    "            common = x - x // d1 - x // d2 + x // lcm\n",
    "            return common >= left1 + left2\n",
    "        return bisect_left(range((uniqueCnt1 + uniqueCnt2) * 2 - 1), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        return bisect.bisect_left(range(2*10**9), True, key=lambda x: ((x-x//divisor1>=uniqueCnt1) and (x-x//divisor2>=uniqueCnt2) and (x-x//lcm(divisor1,divisor2)>=(uniqueCnt1+uniqueCnt2))))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        res1 = (uniqueCnt1 - 1) * divisor1 // (divisor1 - 1) + 1\n",
    "        res2 = (uniqueCnt2 - 1) * divisor2 // (divisor2 - 1) + 1\n",
    "        LCM = lcm(divisor1, divisor2)\n",
    "        res3 = LCM * (uniqueCnt1 + uniqueCnt2 - 1) // (LCM - 1) + 1\n",
    "        return max(res1, res2, res3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            # least common multiple\n",
    "            lcm = math.lcm(divisor1, divisor2)\n",
    "            # accommodate in arr1 but not in arr2\n",
    "            only_arr1 = x // divisor2 - x // lcm\n",
    "            # accommodate in arr2 but not in arr1\n",
    "            only_arr2 = x // divisor1 - x // lcm\n",
    "            # accommodate in both\n",
    "            both_arr = x - (x // divisor1 + x // divisor2 - x // lcm)\n",
    "            # after consuming all only_arr1, arr1 still needs\n",
    "            arr1_need_more = max(uniqueCnt1 - only_arr1, 0)\n",
    "            # after consuming all only_arr2, arr2 still needs\n",
    "            arr2_need_more = max(uniqueCnt2 - only_arr2, 0)\n",
    "\n",
    "            return both_arr >= arr1_need_more + arr2_need_more\n",
    "\n",
    "        left, right = 1, 2 * (10 ** 9)\n",
    "\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            if check(middle):\n",
    "                right = middle - 1\n",
    "            else:\n",
    "                left = middle + 1\n",
    "\n",
    "        return left"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
